We consider the algorithmic problem of selecting a set of target nodes thatcause the biggest activation cascade in a network. In case when the activationprocess obeys the diminishing returns property, a simple hill-climbingselection mechanism has been shown to achieve a provably good performance. Herewe study models of influence propagation that exhibit critical behavior, andwhere the property of diminishing returns does not hold. We demonstrate that insuch systems, the structural properties of networks can play a significantrole. We focus on networks with two loosely coupled communities, and show thatthe double-critical behavior of activation spreading in such systems hassignificant implications for the targeting strategies. In particular, we showthat simple strategies that work well for homogeneous networks can be overlysub-optimal, and suggest simple modification for improving the performance, bytaking into account the community structure.
展开▼
